package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * description:
 * author:张腾
 * date:2021-06-24
 */

/**
 * 给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是 2 。
 */
public class leetcode491 {
    HashSet<List<Integer>> res = new HashSet<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        if (nums.length==0 || nums==null) return new ArrayList<>();
        int n = nums.length;
        dps(nums,0,n);
        return new ArrayList<>(res);
    }

    public void dps(int[] nums,int begin,int len){
        if (path.size()>1) res.add(new ArrayList<>(path));
        if (begin>=len) return;

        for (int i = begin; i < len; i++) {
            boolean flag = false;
            if (!path.isEmpty()){
                if (nums[i]>=path.get(path.size()-1)){
                    path.add(nums[i]);
                    flag = true;
                }
            }else{
                path.add(nums[i]);
                flag = true;
            }
            dps(nums,i+1,len);
            if (flag) path.remove(path.size()-1);
        }
    }
}
